#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        // 计算盘子前缀和
        auto n = s.length();
        vector<int> preSum(n, 0);
        int lastSum = 0;
        for (int idx = 0; idx < n; idx++) {
            if (s[idx] == '*') {
                lastSum++;
            }   
            preSum[idx] = lastSum;
        }

        // 将指定位置处符合要求的蜡烛位置预先处理
        vector<int> left(n, 0);
        int lastLeft = -1;
        for (int idx = 0; idx < n; idx++) {
            if (s[idx] == '|') {
                lastLeft = idx;
            }
            left[idx] = lastLeft;
        }
        vector<int> right(n, 0);
        int lastRight = -1;
        for (int idx = n - 1; idx >= 0 ; idx--) {
            if (s[idx] == '|') {
                lastRight = idx;
            }
            right[idx] = lastRight;
        }

        // 预处理完成，根据给定位置进行查找
        vector<int> ret{};
        for (int idx = 0; idx < queries.size(); idx++) {
            int x = left[queries[idx][1]];
            int y = right[queries[idx][0]];
            if (x == -1 || y == -1 || x <= y) {
                ret.push_back(0);
                continue;
            }
            ret.push_back(preSum[left[queries[idx][1]]] - preSum[right[queries[idx][0]]]);
        }
        return ret;
    }
};

int main()
{
    Solution s;
    string str = "***|**|*****|**||**|*";
    vector<vector<int>> vt = {{1,17},{4,5},{14,17},{5,11},{15,16}};
    vector<int> ret = s.platesBetweenCandles(str, vt);

    for (auto elem : ret) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}